package 子数组问题;

/**
 * @Date 2024/6/8 22:31
 * @description: 环形子数组的最大和
 * .
 * @Author LittleNight
 */
public class likou918 {

    // 最大子数组是基础 https://leetcode.cn/problems/maximum-subarray/description/
    // 题目要求这个子数组非空
    public int maxSubarraySumCircular(int[] nums) {

        int n = nums.length;
        int[] f = new int[n + 1]; // 表示以 i 位置为结尾的所有子数组的最大和
        int[] g = new int[n + 1]; // 最小子数组和 (找出最小值, 然后总和减去最小值就是最大值, 有环的情况)
        f[0] = 0;
        g[0] = 0; // 注意这个题比之前的最大子数组和不同, 那次我们没有添加虚拟节点, 此处我们新加了一个格子, 所以要进行初始化确保后面的值是对的

        int sum = 0;
        int retMax = -0x3f3f3f3f;
        int retMin = 0x3f3f3f3f;
        // 注意这里是多加了一个数组格子, 所以要注意和nums[i]的下标映射
        for (int i = 1; i < n + 1; i++) {
            int x = nums[i - 1];
            sum += x;
            f[i] = Math.max(f[i - 1] + x, x);
            g[i] = Math.min(g[i - 1] + nums[i - 1], nums[i - 1]);
            // 边遍历边更新, dp[0] 是虚拟节点, 不是我们要的答案
            retMax = Math.max(retMax, f[i]);
            retMin = Math.min(retMin, g[i]);
        }
        //if(retMax == retMin) return retMax;
        // 注意有全是负数的情况, 此时sum == retMin. 二者相减为0,但是结果应该是一个负数retMax, 所以进行特判
        if(sum == retMin) return retMax;
        return Math.max(retMax, sum - retMin);
    }
}
